/* 

平均时间复杂度：
    nlogn

最坏时间复杂度：
    n^2

什么情况下最坏：
    快速排序是把数列按一个枢纽值分成两部分分别排序，所以效率高。但是若原数据为有序，并且选择的枢纽值为第一个数时，
    那在分块时会将一个第一个数前面的数（也就是没有）分为一块，将除第一个数的所有数分成了另一块。
    这样一来，每一次分块都只减少了一个值，而每次分块的时间为O（N），所以总时间为O（N^2）。

如何避免：
    虽然随机选取枢轴时，减少出现不好分割的几率，但是还是最坏情况下还是O(n^2），要缓解这种情况，就引入了三数取中选取枢轴。
    三数取中：
    具体思想：对待排序序列中low、mid、high三个位置上数据进行排序，取他们中间的那个数据作为枢轴，并用0下标元素存储枢轴。
    即：采用三数取中，并用0下标元素存储枢轴。
    https://blog.csdn.net/lxk2017/article/details/102779042

*/

// 三数取中函数
const threeNumsSort = function (a, b, c) {
    if (a > b) {
        [a,b] = [b,a];
    } //确定了a<=b
    if (a > c) {
        [a,c] = [c,a];
    } //确定了a<=c
    if (b > c) {
        [b,c] = [c,b];
    } //再判断b和c的值

    return b;
}

const Partition = function (arr, low, high) { //对顺序表中的子表r[low..high]进行一趟排序，返回枢轴位置 
    /* 
        虽然随机选取枢轴时，减少出现不好分割的几率，但是还是最坏情况下还是O(n^2），要缓解这种情况，就引入了三数取中选取枢轴。
        三数取中：
        具体思想：对待排序序列中low、mid、high三个位置上数据进行排序，取他们中间的那个数据作为枢轴，并用0下标元素存储枢轴。
        即：采用三数取中，并用0下标元素存储枢轴。
    */
    if (low >= high) return;

    const mid = Math.floor((low + high) / 2);
    const myMap = new Map([
        [0, low],
        [1, mid],
        [2, high]
    ])
    const tempArr = [arr[low], arr[mid], arr[high]],
        midNums = threeNumsSort(arr[low], arr[mid], arr[high]),
        tempIndex = tempArr.indexOf(midNums);
    [arr[low], arr[myMap.get(tempIndex)]] = [arr[myMap.get(tempIndex)], arr[low]];
    const pivotkey = arr[low];

    while (low < high) //从表的两端交替地向中间扫描 
    {
        while (low < high && arr[high] >= pivotkey) --high;
        arr[low] = arr[high]; //将比枢轴记录小的记录移到低端 
        while (low < high && arr[low] <= pivotkey) ++low;
        arr[high] = arr[low]; //将比枢轴记录大的记录移到高端 
    } //while 

    arr[low] = pivotkey; //枢轴记录到位 
    return low; //返回枢轴位置 
}

function QSort(arr, low, high) { //调用前置初值：low=0; high=arr.length; 
    //对顺序表L中的子序列arr[low..high]做快速排序 
    if (low < high) { //长度大于1 
        pivotloc = Partition(arr, low, high); //将arr[low..high]一分为二，pivotloc是枢轴位置 
        QSort(arr, low, pivotloc - 1);
        QSort(arr, pivotloc + 1, high);
    }
}

function QuickSort(arr) {
    QSort(arr, 0, arr.length - 1);
}

const arr = [49, 38, 65, 97, 76, 13, 27, 49];

QuickSort(arr);

console.log(arr)